package com.ting.test.algorithms.并查集.岛问题;

import com.ting.test.algorithms.并查集.UnionFindByArr;

/**
 * 岛问题
 * <p>
 * 给定一个二维数组matrix，里面的值不是1就是0，
 * 上、下、左、右相邻的1认为是一片岛，
 * 返回matrix中岛的数量
 * 思路，利用并查集，只考虑当前元素的上和左元素
 * 1.如果当前元素和当前元素的上元素或者左元素相当，都为1，则合并
 */
public class 并查集解法1 {
    public static void main(String[] args) {
//        int[][] arr = new int[][]{{1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0}, {1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}};
        int[][] arr = new int[][]{{1,1,1},{1,0,1},{1,1,1}};
        int count = getIslandNums(arr);
        System.out.println(count);
    }

    private static int getIslandNums(int[][] arr) {
        int colLength = arr[0].length;
        int rowLength = arr.length;
        UnionFindByArr unionFindByArr = new UnionFindByArr(arr);


        for (int i = 1; i < colLength; i++) {//第一行元素
            if (arr[0][i] == 1) {
                if (arr[0][i - 1] == 1) {//判断左元素
                    unionFindByArr.union(unionFindByArr.getIndex(arr, 0, i - 1), unionFindByArr.getIndex(arr, 0, i));
                }

            }
        }

        for (int i = 1; i < rowLength; i++) {//第一列元素
            if (arr[i][0] == 1) {
                if (arr[i - 1][0] == 1) {//判断左元素
                    unionFindByArr.union(unionFindByArr.getIndex(arr, i, 0), unionFindByArr.getIndex(arr, i - 1, 0));
                }

            }
        }

        for (int i = 1; i < rowLength; i++) {
            for (int j = 1; j < colLength; j++) {
                if (arr[i][j] == 1) {
                    if (arr[i][j - 1] == 1) {//判断左元素
                        unionFindByArr.union(unionFindByArr.getIndex(arr, i, j), unionFindByArr.getIndex(arr, i, j - 1));
                    }
                    if (arr[i - 1][j] == 1) {//判断上元素
                        unionFindByArr.union(unionFindByArr.getIndex(arr, i, j), unionFindByArr.getIndex(arr, i - 1, j));
                    }
                }
            }
        }
        return unionFindByArr.getSets();
    }


}

